package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 */
public class Solution106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) return null;
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public TreeNode buildTree(int[] inorder, int iStart, int iEnd, int[] postOrder, int pStart, int pEnd) {
        if (iStart > iEnd) return null;
        int curVal = postOrder[pEnd];
        TreeNode cur = new TreeNode(curVal);
        int middle =0;
        for (int i = iStart; i <= iEnd; i++) {
            if (inorder[i] == curVal) {
                middle = i;
                break;
            }
        }
        int rLen = iEnd - middle;
        cur.left = buildTree(inorder, iStart, middle - 1, postOrder, pStart, pEnd - rLen - 1);
        cur.right = buildTree(inorder, middle + 1, iEnd, postOrder, pEnd - rLen, pEnd - 1);
        return cur;
    }

    public static void main(String[] args) {
        int[] inorder = new int[]{9,3,15,20,7};
        int[] postorder = new int[]{9,15,7,20,3};
        System.out.println(new Solution106().buildTree(inorder, postorder));
    }

}
